/*************************************************************************
 * File Name:    Merge_Intervals.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/17 22:11:50
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Merge Intervals
 |
 | Given a collection of intervals, merge all overlapping intervals.
 |
 | For example,
 | Given [1,3],[2,6],[8,10],[15,18],
 | return [1,6],[8,10],[15,18].
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */

bool operator<(const Interval &lhs, const Interval &rhs)
{
    if (lhs.start == rhs.start) return lhs.end < rhs.end;
    return lhs.start < rhs.start;
}

class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals)
    {
        if (intervals.size() == 0) return vector<Interval>();
        
        sort(intervals.begin(), intervals.end());
        
        vector<Interval> ans;
        Interval t = intervals[0];
        
        for (size_t i = 1; i < intervals.size(); ++i) {
            if (intervals[i].start <= t.end) {
                t.end = max(intervals[i].end, t.end);
            } else {
                ans.push_back(t);
                t = intervals[i];
            }
        }
        ans.push_back(t);
        return ans;
    }
};

